'''
Created on 21/09/2013

@author: daniel
'''
import unittest
import parte1ej4ej5.funcionesArbolBinario
import colecciones.pila
import copy

class ArbolAVL(parte1ej4ej5.funcionesArbolBinario.FuncionesArbolBinario):
    
    def agregar(self,elem):
        self.add(ArbolAVL(elem))
        desb=self.__esDesBalanceado__()
        if(desb!=None):
            desb.__rebalancear__(elem)
                
    def rotacionSimpleDerecha(self):
        pila=colecciones.pila.Pila()
        if(self.getL()!=None):
            pila.poner(self.getL().getObjeto())
            self.delL()
        if(self.getR().getL()!=None):
            pila.poner(self.getR().getL().getObjeto())
            self.getR().delL()
        if(self.getR().getR().getR()!=None):
            pila.poner(self.getR().getR().getR().getObjeto())
            self.getR().getR().delR()
        pila.poner(self.getR().getR().getObjeto())
        self.getR().delR()
        nvoHijR=self.getObjeto()
        self.nodo.setObjeto(self.getR().getObjeto())
        self.delR()
        self.add(ArbolAVL(nvoHijR))
        while(pila.esVacia()==False):self.add(ArbolAVL(pila.sacar()))
            
    def rotacionSimpleIzquierda(self):
        pila=colecciones.pila.Pila()
        if(self.getR()!=None):
            pila.poner(self.getR().getObjeto())
            self.delR()
        if(self.getL().getR()!=None):
            pila.poner(self.getL().getR().getObjeto())
            self.getL().delR()
        if(self.getL().getL().getL()!=None):
            pila.poner(self.getL().getL().getL().getObjeto())
            self.getL().getL().delL()
        pila.poner(self.getL().getL().getObjeto())
        nvoHijL=copy.deepcopy(self.getObjeto())
        self.nodo.setObjeto(self.getL().getObjeto())
        self.delL()
        self.add(ArbolAVL(nvoHijL))
        while(pila.esVacia()==False):self.add(ArbolAVL(pila.sacar()))
                
    def rotacionDobleDerecha(self):
        pila=colecciones.pila.Pila()
        pila.poner(self.getR().getR().getObjeto())#guardo15
        self.getR().delR()#borro 15
        pila.poner(self.getR().getL().getR().getObjeto())#guardo10
        pila.poner(self.getR().getObjeto())#guardo14
        self.getR().nodo.setObjeto(self.getR().getL().getObjeto())#seteo futura raiz nueva 8        
        self.getR().delL()#borro rama 8 10
        while(pila.esVacia()==False):self.add(ArbolAVL(pila.sacar()))
        pila.poner(self.getL().getObjeto())#guardo 3
        pila.poner(self.getObjeto())#guardo 5
        self.delL()#borro rama 3
        pila.poner(self.getR().getR().getL().getObjeto())
        self.getR().getR().delL()
        pila.poner(self.getR().getR().getR().getObjeto())
        self.getR().getR().getR().delR()
        pila.poner(self.getR().getR().getObjeto())
        self.getR().delR()
        self.nodo.setObjeto(self.getR().getObjeto())
        self.delR()
        while(pila.esVacia()==False):
            self.add(ArbolAVL(pila.sacar()))
            
    def rotacionDobleIzquierda(self):
        pila=colecciones.pila.Pila()
        pila.poner(self.getL().getL().getObjeto())#guardo15
        self.getL().delL()#borro 15
        pila.poner(self.getL().getR().getL().getObjeto())#guardo10
        pila.poner(self.getL().getObjeto())#guardo14
        self.getL().nodo.setObjeto(self.getL().getR().getObjeto())#seteo futura raiz nueva 8        
        self.getL().delR()#borro rama 8 10
        while(pila.esVacia()==False):self.add(ArbolAVL(pila.sacar()))
        pila.poner(self.getR().getObjeto())#guardo 3
        pila.poner(self.getObjeto())#guardo 5
        self.delR()#borro rama 3
        pila.poner(self.getL().getL().getR().getObjeto())
        self.getL().getL().delR()
        pila.poner(self.getL().getL().getL().getObjeto())
        self.getL().getL().getL().delL()
        pila.poner(self.getL().getL().getObjeto())
        self.getL().delL()
        self.nodo.setObjeto(self.getL().getObjeto())
        self.delL()
        while(pila.esVacia()==False):
            self.add(ArbolAVL(pila.sacar()))
            
    
    def __esDesBalanceado__(self):
        '''
        entrega la primer rama desbalanceada
        '''
        desb=None
        if(self.getL()!=None):
            desb=self.getL().__esDesBalanceado__()
        if(self.getR()!=None):
            desb=self.getR().__esDesBalanceado__()
        dif=self.__diferenciaDeNivelesLR__()
        if(desb!=None):return desb
        if((dif>1)|(dif<-1)):return self
        return None
        
    
    def __rebalancear__(self,elem):
        if(self.getL()!=None):
            if(self.getL().getL()!=None):
                if(self.getL().getL().getObjeto() is elem):
                    self.rotacionSimpleIzquierda()
                elif(self.getL().getL().getL()!=None):
                    if(self.getL().getL().getL().getObjeto() is elem):
                        self.rotacionSimpleDerecha()   
            if(self.getL().getR()!=None):
                if(self.getL().getR().getObjeto() is elem):
                    self.rotacionDobleIzquierda()
        if(self.getR()!=None):
            if(self.getR().getR()!=None):
                if(self.getR().getR().getObjeto() is elem):
                    self.rotacionSimpleDerecha()
                elif(self.getR().getR().getR()!=None):
                    if(self.getR().getR().getR().getObjeto() is elem):
                        self.rotacionSimpleDerecha()   
            if(self.getR().getL()!=None):
                if(self.getR().getL().getObjeto() is elem):
                    self.rotacionDobleDerecha()
                                
    def __diferenciaDeNivelesLR__(self):
        if((self.getR()!=None)&(self.getL()!=None)):
            return self.getL().__getNivMax__()-self.getR().__getNivMax__()
        if(self.getR()!=None): return self.nodo.getNivel()-self.getR().__getNivMax__()
        if(self.getL()!=None): return -self.nodo.getNivel()+self.getL().__getNivMax__()
        return 0
    
    def __getNivMax__(self):
        izq=der=0
        if((self.getL()==None)&(self.getR()==None)):
            return self.nodo.getNivel()
        if(self.getL()!=None): izq= self.getL().__getNivMax__()
        if(self.getR()!=None): der= self.getR().__getNivMax__()
        if(der>izq):return der
        return izq
    
class Test(unittest.TestCase):

    def testInit(self):
        '''
        Se verifica constructor
        '''
        obj=ArbolAVL(None)
        self.assertIsInstance(obj, ArbolAVL, "Se verifica la creacion del arbol")
  
    def testAgregar(self):
        '''
        se utiliza el metodo agragar para armar el ArbolAVL y se verifica alternadamente
        '''
        obj=ArbolAVL(1)
        self.assertEquals(obj.getObjeto(), 1, "Verifica raiz correcta")
        obj.agregar(2)
        self.assertEquals(obj.getR().getObjeto(),2, "Verifica incersion correcta")
        obj.agregar(3)
        self.assertEquals(obj.getObjeto(), 2, "Verifica raiz correcta")
        self.assertEquals(obj.getL().getObjeto(), 1, "Verifica hijo l correcta")
        self.assertEquals(obj.getR().getObjeto(), 3, "Verifica hijo r correcta")
        self.assertIsNone(obj.getL().getR(), "Verifica None correcta")
        obj.agregar(4)
        self.assertEquals(obj.getObjeto(), 2, "Verifica raiz correcta")
        self.assertEquals(obj.getL().getObjeto(), 1, "Verifica hijo l correcta")
        self.assertEquals(obj.getR().getObjeto(), 3, "Verifica hijo r correcta")
        self.assertEquals(obj.getR().getR().getObjeto(), 4, "Verifica nieto rr correcta")
        obj.agregar(5)
        self.assertEquals(obj.getObjeto(), 2, "Verifica raiz correcta")
        self.assertEquals(obj.getL().getObjeto(), 1, "Verifica hijo l correcta")
        self.assertEquals(obj.getR().getObjeto(), 4, "Verifica hijo r correcta")
        self.assertEquals(obj.getR().getR().getObjeto(), 5, "Verifica nieto rr correcta")
        self.assertEquals(obj.getR().getL().getObjeto(), 3, "Verifica nieto lr correcta")
        obj.agregar(6)
        self.assertEquals(obj.getObjeto(), 4, "Verifica raiz correcta")
        obj.agregar(7)
        self.assertEquals(obj.getObjeto(), 4, "Verifica raiz correcta")
        obj.agregar(8)
        self.assertEquals(obj.getObjeto(), 4, "Verifica raiz correcta")
                    
    def testRotacionSimpleIzquierda(self):
        '''
        se arma un arbol binario con 3,2,1 y se le aplica el metodo rotacionSimpleIzquierda()
        para obtener un ArbolABL
        '''
        obj=ArbolAVL(3)
        self.assertEquals(obj.getObjeto(), 3, "Verifica raiz correcta")
        obj.add(ArbolAVL(2))
        self.assertEquals(obj.getL().getObjeto(),2, "Verifica incersion correcta")
        obj.add(ArbolAVL(1))
        obj.rotacionSimpleIzquierda()
        self.assertEquals(obj.getObjeto(), 2, "Verifica raiz correcta")
        self.assertEquals(obj.getL().getObjeto(), 1, "Verifica hijo l correcta")
        self.assertEquals(obj.getR().getObjeto(), 3, "Verifica hijo r correcta")
   
    def testRotacionSimpleDerecha(self):
        '''
        se arma un arbol binario con 1,2,3 y se le aplica el metodo rotacionSimpleDerecha()
        para obtener un ArbolABL
        '''
        obj=ArbolAVL(1)
        self.assertEquals(obj.getObjeto(), 1, "Verifica raiz correcta")
        obj.add(ArbolAVL(2))
        self.assertEquals(obj.getR().getObjeto(),2, "Verifica incersion correcta")
        obj.add(ArbolAVL(3))
        obj.rotacionSimpleDerecha()
        self.assertEquals(obj.getObjeto(), 2, "Verifica raiz correcta")
        self.assertEquals(obj.getL().getObjeto(), 1, "Verifica hijo l correcta")
        self.assertEquals(obj.getR().getObjeto(), 3, "Verifica hijo r correcta")
   
       
    def testRotacionDobleIzquierda(self):
        '''
        se arma arbol binario
              19
             / \
           15  20
          / \
         8  18
            /
          16
        Y se le aplica el metodo obj.rotacionDobleIzquierda() para obtener un ArbolAVL
        '''
        obj=ArbolAVL(19)
        self.assertEquals(obj.getObjeto(), 19, "Verifica raiz correcta")
        obj.add(ArbolAVL(15))
        self.assertEquals(obj.getL().getObjeto(),15, "Verifica incersion correcta")
        obj.add(ArbolAVL(20))
        self.assertEquals(obj.getR().getObjeto(),20, "Verifica incersion correcta")
        obj.add(ArbolAVL(8))
        obj.add(ArbolAVL(18))
        obj.add(ArbolAVL(16))
        obj.rotacionDobleIzquierda()
        self.assertEquals(obj.getObjeto(), 18, "Verifica raiz correcta")
        self.assertEquals(obj.getL().getObjeto(), 15, "Verifica hijo l correcta")
        self.assertEquals(obj.getR().getObjeto(), 19, "Verifica hijo r correcta")
       
    def testRotacionDobleDerecha(self):
        '''
        se arma arbol binario
          5
         / \
        3  14
          / \
         8  15
          \
          10
        Y se le aplica el metodo obj.rotacionDobleDerecha() para obtener un ArbolAVL
        '''
        obj=ArbolAVL(5)
        self.assertEquals(obj.getObjeto(), 5, "Verifica raiz correcta")
        obj.add(ArbolAVL(3))
        self.assertEquals(obj.getL().getObjeto(),3, "Verifica incersion correcta")
        obj.add(ArbolAVL(14))
        self.assertEquals(obj.getR().getObjeto(),14, "Verifica incersion correcta")
        obj.add(ArbolAVL(8))
        obj.add(ArbolAVL(15))
        obj.add(ArbolAVL(10))
        obj.rotacionDobleDerecha()
        self.assertEquals(obj.getObjeto(), 8, "Verifica raiz correcta")
        self.assertEquals(obj.getL().getObjeto(), 5, "Verifica hijo l correcta")
        self.assertEquals(obj.getR().getObjeto(), 14, "Verifica hijo r correcta")
       
    def testGetNivelMaximo(self):
        '''
        se arma un arbol binario y se verifica la devolucion de la funcion __getNivMax__()
        '''
        obj=ArbolAVL(5)
        self.assertEquals(obj.__getNivMax__(),0,"Verifica nivel de arbol con un elemento")
        self.assertEquals(obj.getObjeto(), 5, "Verifica raiz correcta")
        obj.add(ArbolAVL(3))
        self.assertEquals(obj.getL().getObjeto(),3, "Verifica incersion correcta")
        obj.add(ArbolAVL(14))
        self.assertEquals(obj.getR().getObjeto(),14, "Verifica incersion correcta")
        obj.add(ArbolAVL(8))
        obj.add(ArbolAVL(15))
        obj.add(ArbolAVL(10))
        self.assertEquals(obj.getL().__getNivMax__(), 1, "verifica correcta devolucion de profundidad")
        self.assertEquals(obj.__getNivMax__(), 3, "verifica correcta devolucion de profundidad")
        self.assertEquals(obj.getR().__getNivMax__(), 3, "verifica correcta devolucion de profundidad")
   
    def testDiferenciaDeNivelesLR(self):
        '''
        se arma arbol binario y se prueba la devolucion de la funcion __diferenciaDeNivelesLR__()
        '''
        obj=ArbolAVL(5)
        self.assertEquals(obj.getObjeto(), 5, "Verifica raiz correcta")
        obj.add(ArbolAVL(3))
        self.assertEquals(obj.getL().getObjeto(),3, "Verifica incersion correcta")
        obj.add(ArbolAVL(14))
        self.assertEquals(obj.getR().getObjeto(),14, "Verifica incersion correcta")
        obj.add(ArbolAVL(8))
        obj.add(ArbolAVL(15))
        obj.add(ArbolAVL(10))
        obj.add(ArbolAVL(11))
        self.assertEquals(obj.__diferenciaDeNivelesLR__(),-3,"verifica diferencia de niveles")
        self.assertEquals(obj.getR().__diferenciaDeNivelesLR__(),2,"verifica diferencia de niveles")
        self.assertEquals(obj.getR().getL().__diferenciaDeNivelesLR__(),-2,"verifica diferencia de niveles")
         
    def testEsDesbalanceado(self):
        '''
        se arman 2 arboles binarios obj1 y obj2, desbalanceados y se le aplica la funcion
        __esDesBalanceado() para ver si entrega la rama desbalanceada
        '''
        obj1=ArbolAVL(2)
        self.assertEquals(obj1.getObjeto(), 2, "Verifica raiz correcta")
        obj1.add(ArbolAVL(1))
        self.assertEquals(obj1.getL().getObjeto(),1, "Verifica incersion correcta")
        obj1.add(ArbolAVL(3))
        obj1.add(ArbolAVL(4))
        obj1.add(ArbolAVL(5))
 
        arb=obj1.__esDesBalanceado__()
        self.assertIsNotNone(arb, "verifica que encontro el nivel desbalanceado")
        self.assertEquals(arb.getObjeto(), 3, "Verifica el nodo desbalanceado")
         
        obj2=ArbolAVL(2)
        self.assertEquals(obj2.getObjeto(), 2, "Verifica raiz correcta")
        obj2.add(ArbolAVL(1))
        self.assertEquals(obj2.getL().getObjeto(),1, "Verifica incersion correcta")
        obj2.add(ArbolAVL(4))
        obj2.add(ArbolAVL(3))
        obj2.add(ArbolAVL(5))
        self.assertIsNone(obj2.__esDesBalanceado__(),"Verifica arbol balanceado")
        obj2.add(ArbolAVL(6))
        self.assertEquals(obj2.__esDesBalanceado__().getObjeto(),2, "Verifica raiz desb")
     
    def testRebalancear(self):
        '''
        En obj1 se arma un arbol binario
          2
         / \
        1  3
            \
            4
             \
              5
        Y se le aplica el metodo obj1.__rebalancear__() para obtener un ArbolAVL.
        Luego en obj2 se arma otro arbol binario
          2
         / \
        1  4
          / \
         3  5
             \
             6
        Y se le aplica el metodo obj2.__rebalancear__() para obtener un ArbolAVL
        '''
        obj1=ArbolAVL(2)
        self.assertEquals(obj1.getObjeto(), 2, "Verifica raiz correcta")
        obj1.add(ArbolAVL(1))
        self.assertEquals(obj1.getL().getObjeto(),1, "Verifica incersion correcta")
        obj1.add(ArbolAVL(3))
        obj1.add(ArbolAVL(4))
        obj1.add(ArbolAVL(5))

        self.assertEquals(obj1.__esDesBalanceado__().getObjeto(), 3, "Verifica el nodo desbalanceado")
        obj1.getR().__rebalancear__(5)
        self.assertIsNone(obj1.__esDesBalanceado__(),"Verifica desbalanceo corregido")
                
        obj2=ArbolAVL(2)
        self.assertEquals(obj2.getObjeto(), 2, "Verifica raiz correcta")
        obj2.add(ArbolAVL(1))
        self.assertEquals(obj2.getL().getObjeto(),1, "Verifica incersion correcta")
        obj2.add(ArbolAVL(4))
        obj2.add(ArbolAVL(3))
        obj2.add(ArbolAVL(5))
        self.assertIsNone(obj2.__esDesBalanceado__(),"Verifica arbol balanceado")
        obj2.add(ArbolAVL(6))
        
        self.assertEquals(obj2.__esDesBalanceado__().getObjeto(),2, "Verifica raiz desb")
        self.assertEquals(obj2.getR().getR().getR().getObjeto(), 6, "Verifica condicion rotacion simple")
        obj2.__rebalancear__(6)
        self.assertIsNone(obj2.__esDesBalanceado__(),"Verifica arbol balanceado")
        
if __name__ == "__main__":
    #import sys;sys.argv = ['', 'Test.testName']
    unittest.main()